# 链表实现双向队列
class ListNode:
    """
    双向链表节点
    """

    def __init__(self, val: int):
        self.val: int = val
        self.next: ListNode | None = None  # 后继节点引用
        self.prev: ListNode | None = None  # 前驱节点引用


class LinkedListDeque:
    """基于双向链表实现的双向队列"""

    def __init__(self):
        """构造方法"""
        self._front: ListNode | None = None  # 头节点
        self._rear: ListNode | None = None  # 尾节点
        self._size: int = 0

    def size(self) -> int:
        """获取双向队列的长度"""
        return self._size

    def is_empty(self) -> bool:
        """判断双向队列是否为空"""
        return self._size == 0

    def push(self, num: int, is_front: bool = False):
        """入队操作"""
        node = ListNode(num)
        # 若链表为空, 则令 front 和 rear 都指向 node
        if self.is_empty():
            self._front = self._rear = node
        # 队首入队操作
        elif is_front:
            # 将 node 添加至链表头部
            self._front.prev = node
            node.next = self._front
            self._front = node  # 更新头结点
        # 队尾入队操作
        else:
            # 将 node 添加至链表尾部
            self._rear.next = node
            node.prev = self._rear
            self._rear = node  # 更新尾结点
        self._size += 1  # 更新队列长度

    def pop(self, is_front: bool = False) -> int:
        """出队操作"""
        # 队列为空, 直接返回 -1
        if self.is_empty():
            raise IndexError("双向队列为空")
        # 队首出队操作
        if is_front:
            val: int = self._front.val  # 暂存头节点的值
            # 删除头节点
            front_next: ListNode | None = self._front.next
            if front_next is not None:
                front_next.prev = None
                self._front.next = None
            self._front = front_next  # 更新头结点
        # 尾部出队操作
        else:
            val: int = self._rear.val  # 暂存尾节点的值
            # 删除尾节点
            rear_prev: ListNode | None = self._rear.prev
            if rear_prev is not None:
                rear_prev.next = None
                self._rear.prev = None
            self._rear = rear_prev  # 更新尾结点
        self._size -= 1  # 更新队列长度
        return val

    def push_first(self, num: int):
        """队首入队操作"""
        self.push(num, is_front=True)

    def push_last(self, num: int):
        """队尾入队操作"""
        self.push(num, is_front=False)

    def pop_first(self) -> int:
        """队首出队操作"""
        return self.pop(is_front=True)

    def pop_last(self) -> int:
        """队尾出队操作"""
        return self.pop(is_front=False)

    def peek_first(self) -> int:
        """获取队首元素"""
        if self.is_empty():
            raise IndexError("双向队列为空")
        return self._front.val

    def peek_last(self) -> int:
        """获取队尾元素"""
        if self.is_empty():
            raise IndexError("双向队列为空")
        return self._rear.val

    def to_array(self) -> list[int]:
        """将双向队列转换为数组"""
        arr: list[int] = []
        cur: ListNode | None = self._front
        while cur is not None:
            arr.append(cur.val)
            cur = cur.next
        return arr


